package com.algorithms.binarytrees;

import com.algorithms.linkedlists.LinkedQueue;
import com.algorithms.utils.AlgorithmException;

public class BinaryTree<T> {
	private Node<T> root;
	
	public BinaryTree(){
		this.root = null;
	}
	
	public BinaryTree(int rootKey){
		this.root = new Node<T>(rootKey);
	}
	
	public BinaryTree(int rootKey, T rootValue){
		this.root = new Node<T>(rootKey, rootValue);
	}
	
	/**
	 * find a node from the binary tree using key
	 * 
	 * @param key
	 * @return
	 */
	public T find(int key){
		Node<T> curr = this.root;
		while (curr != null){
			if (key == curr.getKey()){
				return curr.getValue();
			}
			else if (key < curr.getKey()){
				curr = curr.getLeftChild();
			}else if (key > curr.getKey()){
				curr = curr.getRightChild();
			}
		}
		return null;	// no node is found
	}
	
	/**
	 * insert a node (key, value) into the binary tree
	 * 
	 * @param key
	 * @param value
	 */
	public void insert(int key, T value){
		Node<T> newNode = new Node<T>(key, value);
		if (this.root == null){
			this.root = newNode;
			return;
		}else{
			Node<T> currVisitNode = this.root;
			while (true){
				if (key < currVisitNode.getKey()){
					if (currVisitNode.getLeftChild() != null){
						currVisitNode = currVisitNode.getLeftChild();
					}else{
						currVisitNode.setLeftChild(newNode);
						break;
					}
				}else{
					if (currVisitNode.getRightChild() != null){
						currVisitNode = currVisitNode.getRightChild();
					}else{
						currVisitNode.setRightChild(newNode);
						break;
					}
				}
			}
		}
	}
	
	/**
	 * delete a node out of the binary tree
	 * 
	 * @param key
	 * @return
	 * @throws AlgorithmException
	 */
	public Node<T> delete(int key) throws AlgorithmException {
		FoundNodes foundNodes = findInner(key);
		
		// if node is not found
		if (foundNodes.foundNode == null){
			throw new AlgorithmException("key is not found in the binary tree");
		}
		
		// if deleting node has no children
		if (foundNodes.foundNode.getLeftChild() == null &&
				foundNodes.foundNode.getRightChild() == null){
			if (foundNodes.parentFoundNode != null){
				if (foundNodes.isLeftNode){
					foundNodes.parentFoundNode.setLeftChild(null);
				}else{
					foundNodes.parentFoundNode.setRightChild(null);
				}
			}else{
				// deleting node is root node
				this.root = null;
			}
			return foundNodes.foundNode;
		}
		
		// if deleting node has only left child
		if (foundNodes.foundNode.getLeftChild() != null && 
				foundNodes.foundNode.getRightChild() == null){
			if (foundNodes.parentFoundNode != null){
				if (foundNodes.isLeftNode){
					foundNodes.parentFoundNode.setLeftChild(
							foundNodes.foundNode.getLeftChild());
				}else{
					foundNodes.parentFoundNode.setRightChild(
							foundNodes.foundNode.getLeftChild());
				}
			}else{
				// delete at root
				this.root = foundNodes.foundNode.getLeftChild();
			}
			
			return foundNodes.foundNode;
		}
		
		// if deleting node has only right child
		if (foundNodes.foundNode.getLeftChild() == null && 
				foundNodes.foundNode.getRightChild() != null){
			if (foundNodes.parentFoundNode != null){
				if (foundNodes.isLeftNode){
					foundNodes.parentFoundNode.setLeftChild(
							foundNodes.foundNode.getRightChild());
				}else{
					foundNodes.parentFoundNode.setRightChild(
							foundNodes.foundNode.getRightChild());
				}
			}else{
				// delete at root
				this.root = foundNodes.foundNode.getRightChild();
			}
			
			return foundNodes.foundNode;
		}
		
		// if the deleting node has both left and right children
		if (foundNodes.foundNode.getLeftChild() != null &&
				foundNodes.foundNode.getRightChild() != null){

			findAndReplace(foundNodes);
			
			return foundNodes.foundNode;
		}
		
		// never ever reach this case
		return null;
	}

	public void traverse(){
		inOrder(this.root);
	}
	
	public void traverseLineByLine(){
		lineByLine();
	}
	
	/**
	 * this will replace a node with its successor node
	 * 
	 * @param key
	 * @return
	 */
	private void findAndReplace(FoundNodes nodeTobeDeleted){
		// find the next right child, it must not be null
		// because this function only works on node that has
		// both children on left and right.
		Node<T> childDeletingNode = nodeTobeDeleted.foundNode.getRightChild();
		
		// find the most left node
		Node<T> successor = childDeletingNode;
		Node<T> successorParent = nodeTobeDeleted.foundNode;
		while (successor.getLeftChild() != null){
			successorParent = successor;
			successor = successor.getLeftChild();
		}
		
		// no more left sub-tree to go
		// connect the parent of deleting node to the successor node
		if (nodeTobeDeleted.parentFoundNode != null){
			if (nodeTobeDeleted.isLeftNode){
				nodeTobeDeleted.parentFoundNode.setLeftChild(successor);
			}else{
				nodeTobeDeleted.parentFoundNode.setRightChild(successor);
			}
		}else{
			this.root = successor;
		}
		
		// add the sub-right tree of successor to the successor
		// position if the sub tree is available
		if (successor.equals(nodeTobeDeleted.foundNode.getRightChild())){
			successorParent.setRightChild(successor.getRightChild());
		}else{
			successorParent.setLeftChild(successor.getRightChild());
		}
		
		// handle over all the children from deleting node
		successor.setLeftChild(nodeTobeDeleted.foundNode.getLeftChild());
		successor.setRightChild(nodeTobeDeleted.foundNode.getRightChild());
	}
	
	/**
	 * this function will find locally a node in the binary tree
	 * with a key.
	 * 
	 * @param key
	 * @return
	 */
	private FoundNodes findInner(int key){
		Node<T> foundNode = this.root;
		Node<T> parentFoundNode = null;
		boolean isLeftNode = false;
		
		while (foundNode != null){
			if (key == foundNode.getKey()){
				return new FoundNodes(foundNode, 
							parentFoundNode, isLeftNode);
			}else{
				parentFoundNode = foundNode;
				if (key < foundNode.getKey()){
					isLeftNode = true;
					foundNode = foundNode.getLeftChild();
				}else if (key > foundNode.getKey()){
					isLeftNode = false;
					foundNode = foundNode.getRightChild();
				}
			}
		}
		return new FoundNodes(null, null);	// no node is found
	}
	
	
	/**
	 * this function will print out the tree line-by-line<br>
	 * the root level at the first line, the next line contains
	 * all items belong to corresponding level.
	 */
	private void lineByLine(){
		LinkedQueue<Node<T>> queue = new LinkedQueue<Node<T>>();
		queue.push(this.root);
		queue.push(null);	// add delimiter
		
		Node<T> node;
		while (true){
			try{
				while ((node = queue.pop()) != null){
					System.out.print(node.getKey() + ", ");
					
					if (node.getLeftChild() != null){
						queue.push(node.getLeftChild());
					}
					
					if (node.getRightChild() != null){
						queue.push(node.getRightChild());
					}
				}
				
				if (queue.isEmpty()){
					break;
				}else{
					queue.push(null);
					System.out.println();
				}
				
			}catch(AlgorithmException alEx){}
		}
	}
	
	/**
	 * this function prints out the binary tree by prefix order
	 * 
	 * @param root
	 */
	private void inOrder(Node<T> root){
		if (root != null){
			inOrder(root.getLeftChild());
			System.out.print(root.getKey() + " ");
			inOrder(root.getRightChild());
		}
	}
	
	/**
	 * this class contains nodes for the inner search.
	 * it is used as struct data type in C++
	 * 
	 * @author minhld
	 *
	 */
	class FoundNodes {
		Node<T> foundNode;
		Node<T> parentFoundNode;
		boolean isLeftNode = false;
		
		public FoundNodes(Node<T> foundNode, Node<T> parentFoundNode){
			this.foundNode = foundNode;
			this.parentFoundNode = parentFoundNode;
			this.isLeftNode = false;
		}

		public FoundNodes(Node<T> foundNode, 
						Node<T> parentFoundNode,
						boolean isLeftNode){
			this.foundNode = foundNode;
			this.parentFoundNode = parentFoundNode;
			this.isLeftNode = isLeftNode;
		}
	}
}
